class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    # 返回构造的TreeNode根节点
    def reConstructBinaryTree(self, pre, tin):
        if not pre:
            return None
        # write code here
        return self.handler(0, len(tin) - 1, pre, tin)

    def handler(self, in_left, in_right, pre, tin):
        if in_left > in_right:
            return None
        root = TreeNode(pre[in_left])
        for k in range(in_left, in_right + 1):
            if root.val == tin[k]:
                root.left = self.handler(in_left+1, k - 1, pre, tin)
                root.right = self.handler(k + 1, in_right, pre, tin)
                break
        return root


if __name__ == '__main__':
    sol = Solution()
    root = sol.reConstructBinaryTree([1, 2, 3, 4, 5, 6, 7], [3, 2, 4, 1, 6, 5, 7])
    print(root)
